package leetcode100

// TODO 队列 [经典] 【-】  二叉树的层序遍历
// TODO https://leetcode.cn/problems/binary-tree-level-order-traversal/solution/tong-guo-fu-zhu-dui-lie-shi-xian-er-cha-ukyld/

func levelOrder(root *TreeNode) [][]int {
    //创建一个空队列，指针数组
    queue := make([]*TreeNode, 0)
    //把根节点放入队列
    queue = append(queue, root)
    //创建一个二维数组
    ans := make([][]int, 0)
    // 第一次将根节点放入队列时，应该先判断根节点是否为 nil。
    if root == nil{
        return ans
    }

    for len(queue) != 0 {
        //用队列长度记录而每层二叉树元素的个数
        //用来作为遍历每层节点放多少次元素进一维数组ans2的次数条件
        size := len(queue)
        //在二叉树当前层创建一个一位数组用来存放当前层的元素
        ans2 := make([]int,0)

        for i:=0; i<size; i++ {
            //因为队首只是一个指针，所以用一个变量存下队首指针
            front := queue[0]
            ans2 = append(ans2, front.Val) //不能用root.val
            //因为每层遍历都需要一个队首的指针来存入数组，存入数组后的队首会被弹出队列
            queue = queue[1:]
            if front.Left != nil {
                queue = append(queue, front.Left)//同理，不能写成root.left。我们要放的是队首的指针，不是根节点的指针。
            }
            if front.Right != nil {
                queue = append(queue, front.Right)
            }
        }
        ans = append(ans, ans2)
    }
    return ans
}